package 算法.其他算法;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class JZ50第一个只出现一次的字符 {
    //哈希表统计频率
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character,Integer> map = new HashMap<>();
        //统计每个字符出现的次数
        for(int i = 0; i < str.length(); i++)
            map.put(str.charAt(i),map.getOrDefault(str.charAt(i),0)+1);
        //找到第一个只出现一次的字母
        for(int i = 0; i < str.length(); i++)
            if(map.get(str.charAt(i)) == 1)
                return i;
        //没有找到
        return -1;
    }

    //队列+哈希表统计位置
    public int FirstNotRepeatingChar2(String str) {
        //统计字符出现的位置
        HashMap<Character, Integer> mp = new HashMap<>();
        Queue<Character> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        for(int i = 0; i < str.length(); i++){
            //没有出现过的字符
            if(!mp.containsKey(str.charAt(i))){
                mp.put(str.charAt(i), i);
                q1.offer(str.charAt(i));
                q2.offer(i);
            }else{
                //找到重复的字符
                //位置置为-1
                mp.put(str.charAt(i), -1);
                //弹出前面所有的重复过的字符
                while(!q1.isEmpty() && mp.get(q1.peek()) == -1){
                    q1.poll();
                    q2.poll();
                }
            }
        }
        return q2.isEmpty() ? -1 : q2.poll();
    }
}
